class Solution {
    /*
        思路：双指针+二分思想
        选左上角，往右走和往下走都增大，不能选

        选右下角，往上走和往左走都减小，不能选

        选左下角，往右走增大，往上走减小，可选

        选右上角，往下走增大，往左走减小，可选
    */
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        int row = 0, col = m-1;
        while( row<n && col>=0 ){
            if( matrix[row][col]<target )
                row++;
            else if( matrix[row][col]>target )
                col--;
            else
                return true;
        }
        return false;
    }
}